package leetCode.offer35;

import java.util.HashMap;


public class Solution1 implements Solution {

    @Override
    public Node copyRandomList(Node head) {
        if(head==null) return null;
        //用于存储
        HashMap<Node,Node> newToOld = new HashMap<>();
        HashMap<Node,Node> oldToNew = new HashMap<>();
        Node current = new Node(head.val);
        Node result = current;
        Node next;
        while(head!=null) {
            if(head.next!=null){
                next = new Node(head.next.val);
            }else{
                next = null;
            }
            current.next = next;
            newToOld.put(current,head);
            oldToNew.put(head,current);
            current = next;
            head = head.next;
        }
        current = result;
        while(current!=null){
            current.random = oldToNew.get(newToOld.get(current).random);
            current = current.next;
        }
        return result;
    }
}
